﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<cstring>
using namespace std;
//P3146 区间dp 核心：f的定义 
//int n;
//const int N = 250;
//int a[N];
//int f[N][N];//f表示 i-j能合并成一个值的最大值 0表示状态非法 结果的位置不确定 需要随时更新
//int main()
//{
//	cin >> n;
//	int ret = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i]; 
//		f[i][i] = a[i]; //对角线上的值等于其自己
//		ret = max(ret, a[i]);//可能合并了的值还不如原先的最大值
//	}
//	for(int len=1;len<=n;len++)
//		for (int i = 1; i + len - 1 <= n; i++)
//		{
//			int j = i + len - 1;
//			//以k为第一段的终点 把区间划分为两段
//			for (int k = i; k < j; k++)
//			{
//				if (f[i][k] && f[k + 1][j] && f[i][k] == f[k + 1][j])//两个区间都可以合并 且两个区间合并后数值相等
//				{
//					f[i][j] = max(f[i][j], f[i][k] + 1);
//					ret = max(ret, f[i][j]);
//				}
//			}
//		}
//	cout << ret << endl;
//	return 0;
//}
//P1880 狮子合并 采用倍增来处理环形问题 其余思想同上题
//int n;
//const int N = 210;//处理圆形问题 数组存两倍就可以了
//int s[N];//前缀和数组 把圆环存下来
//int f[N][N];//最小值
//int g[N][N];//最大值
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> s[i];
//		s[i + n] = s[i];
//	}
//	int m = n + n;
//	for (int i = 1; i <= m; i++)
//	{
//		s[i] += s[i - 1];
//	}
//	
//	memset(f, 0x3f, sizeof f);
//	memset(g, -0x3f, sizeof g);
//	for (int i = 1; i <= m; i++)f[i][i] = g[i][i] = 0;
//	
//	for (int len = 1; len <= n; len++)//控制len的长度
//		for (int i = 1; i + len - 1 <= m; i++)
//		{
//			int j = i + len - 1;
//			int t = s[j] - s[i - 1];
//			for (int k = i; k < j; k++)
//			{
//				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + t);
//				g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + t);
//			}
//		}
//	int ret1 = 0x3f3f3f3f; int ret2 = 0;
//	for (int i = 1; i <= n; i++)//极值不再只限于[1][n] 需要遍历一下[i][i+n-1]
//	{
//		ret1 = min(ret1, f[i][i + n - 1]);
//		ret2 = max(ret2, g[i][i + n - 1]);
//	}
//	cout << ret1 << endl << ret2 << endl;
//	return 0;
//}

//P1775 柿子合并 弱化版 选择一个点来划分区间 和选取左右端点划分不同
//int n;
//const int N = 310;
//int a[N];//当前缀和数组用
//int f[N][N];//f表示把1-n的区间合并的最小代价
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		int x; cin >> x;
//		a[i] = x + a[i - 1];//我的前缀和是不是写错了 好的 没有 用的时候注意一下就行 a[j] - a[i-1]
//	}
//	//初始化 求最小值 全初始化为正无穷 当len=1时 只剩下一堆 此时不需要代价即可 设置为0
//	memset(f, 0x3f, sizeof f);
//	for (int i = 1; i <= n; i++)f[i][i] = 0;
//	for(int len=2;len<=n;len++)
//		for (int i = 1; i + len - 1 <= n; i++)
//		{
//			int j = i + len - 1;
//			int t = a[j] - a[i - 1];
//			for (int k = i; k < j; k++)//划分方式为找到k点 把区间划分为两块 左边包含k点 右边不包含k点
//			{
//				//左区间合并的代价+右区间合并的代价+两堆合并的代价
//				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + t);
//			}
//		}
//	cout << f[1][n] << endl;
//	return 0;
//}
//P2858 区间养牛 确定f表达含义即可 画图确定初始化
//int n;
//const int N = 2010;
//int a[N],f[N][N];//f表示在【i-j】的区间内，销售物品的最大价值
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)cin >> a[i];
//	//初始化默认为0即可
//	for(int len=1;len<=n;len++)
//		for (int i = 1; i + len - 1 <= n; i++)//确保区间不越界
//		{
//			int j = i + len - 1;//右端点
//			int d = n - len + 1;//天数
//			//要么取左边 要么取右边
//			f[i][j] = max(f[i + 1][j]+d*a[i], f[i][j - 1]+d*a[j]);
//		}
//	cout << f[1][n] << endl;
//	return 0;
//}
//P1435 回文串 区间dp
//const int N = 1010;
//int f[N][N];//f表示 字符串 [i, j] 区间，变成回⽂串的最⼩插⼊次数
//string s;
//int main()
//{
//	cin >> s;
//	int n = s.size();
//	s = " " + s;
//	for(int len=2;len<=n;len++)//以区间长度来填表 本题中初始化默认为0即可 画图确认 同时可以从len=2开始循环
//		for (int i = 1; i + len - 1 <= n; i++)//枚举左端点 
//		{
//			int j = i + len - 1;//右端点 
//			if (s[i] == s[j])f[i][j] = f[i + 1][j - 1];
//			else f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
//		}
//	cout << f[1][n] << endl;
//	return 0;
//}
//P1910 多维背包 
//int n, m, x;
//const int N = 1010;
//int f[N][N];//两个限制条件 二维背包问题 f表示不超过m和x情况下的最大价值
//int a[N], b[N], c[N];
//int main()
//{
//	cin >> n >> m >> x;
//	for (int i = 1; i <= n; i++)cin >> a[i] >> b[i] >> c[i];
//	for (int i = 1; i <= n; i++)//01背包 从大到小遍历
//		for (int j = m; j >= b[i]; j--)
//			for (int k = x; k >= c[i]; k--)
//			{
//				f[j][k] = max(f[j][k], f[j - b[i]][k - c[i]]+a[i]);
//			}
//	cout << f[m][x] << endl;
//	return 0;
//}
//P1833 混合背包问题 分类讨论即可
//int n, m;
//const int N = 1e4 + 10,T=1010;
//int t[N], v[N], p[N];
//int f[N][T];
//int time_(string s)
//{
//	int i; int t1 = 0; int t2 = 0;
//	for (i = 0; i < s.size() && s[i] != ':'; i++)
//	{
//		t1 = t1 * 10 + (s[i] - '0');
//	}
//	t1 *= 60; i++;
//	for (; i < s.size(); i++)
//	{
//		t2 = t2 * 10 + (s[i] - '0');
//	}
//	return t1 + t2;
//}
//int main()
//{
//	string s1, s2;
//	cin >> s1 >> s2 >> n;
//	m = time_(s2) - time_(s1);
//	for (int i = 1; i <= n; i++)cin >> t[i] >> v[i] >> p[i];
//	for(int i=1;i<=n;i++)
//		for (int j=0;j<=m;j++)
//		{
//			f[i][j] = f[i - 1][j];//上来都先不选
//			if (p[i] == 0)//完全背包//必须从左往右
//			{
//				if(j>=t[i])f[i][j] = max(f[i][j], f[i][j - t[i]] + v[i]);//注意细节
//			}
//			else//多重背包（01背包也是多重背包）
//			{
//				for (int k = 1; k <= p[i] && j >= k * t[i]; k++)
//					f[i][j] = max(f[i][j], f[i - 1][j - k*t[i]] + k*v[i]);
//			}
//		}
//	cout << f[n][m] << endl;
//	return 0;
//}